The present invention relates generally to data processing systems and software optimization, and in particular to a method and system for configuring and for using a data dependency graph (“DDG”) for dynamic by-pass instruction scheduling.
As known to those skilled in the art, a DDG is a type of directed acyclic weighted graph that may be used to represent relationships between instructions during scheduling. For example, a DDG may contain a plurality of nodes representing instructions within a “basic block” containing straight-line execution code. Directed edges between the nodes in the DDG identify causal dependencies (by convention, a “successor” node has a causal dependency upon a “predecessor” node).
The edges between a pair of nodes may be annotated with “weights” representing a sum of delays and latencies between the nodes. Delay is incurred, for example, as a result of pipeline stalls that typically occur when an instruction requires the results of another instruction before it can execute. Latency is a characteristic lag time resulting from the execution of an instruction. Both delay and latency may be measured in the same time unit, namely execution cycles, and may be summed together to obtain the “weight” or total time in cycles.
Given a DDG representing a basic block of instructions, a heuristic function can be used to rank nodes representing instructions in the DDG for the purposes of scheduling those instructions. In a commonly used heuristic function, nodes in the DDG are ranked based on the “critical path” length of a node. Generally speaking, the critical path for a node “i” in a DDG (representing an instruction “i”) is defined as the sum of the weights of edges along a path from node “i” to the furthest leaf node in the graph (i.e. to a node having no further edge connections to other nodes in the DDG). As known in the art, scheduling may be prioritized so that instructions (i.e. nodes in the DDG) with longer critical paths are scheduled first. This scheduling strategy assumes that executing instructions with the longest critical paths first will generally tend to minimize the total execution time for a given set of instructions.
A closely related concept in instruction scheduling based on DDG analysis is an “earliest time” for an instruction. Generally speaking, the earliest time for a node “i” in a DDG (representing an instruction “i”) is the earliest execution cycle in which instruction “i” may be scheduled in view of causal dependencies with predecessor nodes.
Known scheduling techniques based on DDG analysis are limited in that they generally support only delays that are fixed when a DDG is first created. These known techniques are not optimal for handling delays that can change dynamically, such as may be found in some modern computer architectures permitting dynamic by-pass execution. (Such computer architectures permit a delay between a by-pass pair of instructions to change dynamically between a full delay and a zero delay, as explained in further detail below.)
What is needed is a technique for configuring a dependency graph to handle instruction scheduling in architectures permitting such dynamic by-pass execution.